home *** CD-ROM | disk | FTP | other *** search
RRRRWWWWTTTTVVVVaaaallllHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333CCCC++++++++)))) RRRRWWWWTTTTVVVVaaaallllHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333CCCC++++++++)))) NNNNaaaammmmeeee RWTValHashTable<T> - Rogue Wave library class SSSSyyyynnnnooooppppssssiiiissss #include <rw/tvhasht.h> unsigned hashFun(const T&); RWTValHashTable<T> table(hashFun); PPPPlllleeeeaaaasssseeee NNNNooootttteeee!!!! IIIIffff yyyyoooouuuu ddddoooo nnnnooootttt hhhhaaaavvvveeee tttthhhheeee SSSSttttaaaannnnddddaaaarrrrdddd CCCC++++++++ LLLLiiiibbbbrrrraaaarrrryyyy,,,, uuuusssseeee tttthhhheeee iiiinnnntttteeeerrrrffffaaaacccceeee ddddeeeessssccccrrrriiiibbbbeeeedddd hhhheeeerrrreeee.... OOOOtttthhhheeeerrrrwwwwiiiisssseeee,,,, uuuusssseeee tttthhhheeee iiiinnnntttteeeerrrrffffaaaacccceeee ttttoooo RRRRWWWWTTTTVVVVaaaallllHHHHaaaasssshhhhMMMMuuuullllttttiiiiSSSSeeeetttt described in the Class Reference. DDDDeeeessssccccrrrriiiippppttttiiiioooonnnn This class implements a parameterized hash table of types TTTT. It uses chaining to resolve hash collisions. Duplicates are allowed. It is a vvvvaaaalllluuuueeee based collection: objects are copied in and out of the hash buckets. Parameter TTTT represents the type of object to be inserted into the table, either a class or fundamental type. The class TTTT must have: well-defined copy semantics (TTTT::::::::TTTT((((ccccoooonnnnsssstttt TTTT&&&&)))) or equivalent); well-defined assignment semantics (TTTT::::::::ooooppppeeeerrrraaaattttoooorrrr====((((ccccoooonnnnsssstttt TTTT&&&&)))) or equivalent); well-defined equality semantics (TTTT::::::::ooooppppeeeerrrraaaattttoooorrrr========((((ccccoooonnnnsssstttt TTTT&&&&))))). A user-supplied hashing function for type TTTT must be supplied to the constructor when creating a new table. If TTTT is a Rogue Wave class, then this requirement is usually trivial because most Rogue Wave objects know how to return a hashing value. In fact, classes RRRRWWWWCCCCSSSSttttrrrriiiinnnngggg, RRRRWWWWDDDDaaaatttteeee, RRRRWWWWTTTTiiiimmmmeeee, and RRRRWWWWWWWWSSSSttttrrrriiiinnnngggg contain static member functions called hhhhaaaasssshhhh that can be supplied to the constructor as is. The function must have prototype:.Ex unsigned hhhhFFFFuuuunnnn(const T& a); and should return a suitable hash value for the object aaaa. To find an object, it is first hashed to determine in which bucket it occurs. The bucket is then searched for an object that is equal (as determined by the equality operator) to the candidate. The initial number of buckets in the table is set by the constructor. There is a default value. If the number of items in the collection greatly exceeds the number of buckets then efficiency will sag because each bucket must be searched linearly. The number of buckets can be changed by calling member function rrrreeeessssiiiizzzzeeee(((()))). This is an expensive proposition because not only must all items be PPPPaaaaggggeeee 1111 RRRRWWWWTTTTVVVVaaaallllHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333CCCC++++++++)))) RRRRWWWWTTTTVVVVaaaallllHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333CCCC++++++++)))) copied into the new buckets, but they must also be rehashed. If you wish this to be automatically done, then you can subclass from this class and implement your own special iiiinnnnsssseeeerrrrtttt(((()))) and rrrreeeemmmmoooovvvveeee(((()))) functions which perform a rrrreeeessssiiiizzzzeeee(((()))) as necessary. PPPPeeeerrrrssssiiiisssstttteeeennnncccceeee None EEEExxxxaaaammmmpppplllleeee #include <rw/tvhasht.h> #include <rw/cstring.h> #include <rw/rstream.h> main() { RWTValHashTable<RWCString> table(RWCString::hash); table.insert("Alabama"); // NB: Type conversion occurs table.insert("Pennsylvania"); table.insert("Oregon"); table.insert("Montana"); cout << "The table " << (table.contains("Oregon") ? "does " : "does not ") << "contain Oregon0; table.removeAll("Oregon"); cout << "Now the table " << (table.contains("Oregon") ? "does " : "does not ") << "contain Oregon"; return 0; } Program output The table does contain Oregon Now the table does not contain Oregon PPPPuuuubbbblllliiiicccc CCCCoooonnnnssssttttrrrruuuuccccttttoooorrrrssss RRRRWWWWTTTTVVVVaaaallllHHHHaaaasssshhhhTTTTaaaabbbblllleeee<T>(unsigned (*hashFun)(const T&), size_t buckets = RWDEFAULT_CAPACITY); Constructs a new hash table. The first argument is a pointer to a user- defined hashing function for items of type TTTT.... The table will initally have bbbbuuuucccckkkkeeeettttssss buckets although this can be changed with member function rrrreeeessssiiiizzzzeeee(((()))). RRRRWWWWTTTTVVVVaaaallllHHHHaaaasssshhhhTTTTaaaabbbblllleeee<T>(const RWTValHashTable<T>& table); Constructs a new hash table as a copy of ttttaaaabbbblllleeee. The new table will have the same number of buckets as the old table. Hence, although objects PPPPaaaaggggeeee 2222 RRRRWWWWTTTTVVVVaaaallllHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333CCCC++++++++)))) RRRRWWWWTTTTVVVVaaaallllHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333CCCC++++++++)))) must be copied into the new table, they will not be hashed. PPPPuuuubbbblllliiiicccc OOOOppppeeeerrrraaaattttoooorrrrssss RWTValHashTable& ooooppppeeeerrrraaaattttoooorrrr====(const RWTValHashTable<T>&); Sets self to a copy of ttttaaaabbbblllleeee. Afterwards, the new table will have the same number of buckets as the old table. Hence, although objects must be copied into the new table, they will not be hashed. PPPPuuuubbbblllliiiicccc MMMMeeeemmmmbbbbeeeerrrr FFFFuuuunnnnccccttttiiiioooonnnnssss void aaaappppppppllllyyyy(void (*applyFun)(T&, void*), void* d); Applies the user-defined function pointed to by aaaappppppppllllyyyyFFFFuuuunnnn to every item in the table. This function must have prototype: void yyyyoooouuuurrrrFFFFuuuunnnn(T& a, void* d); Client data may be passed through as parameter dddd. void cccclllleeeeaaaarrrr(); Removes all items from the collection. RWBoolean ccccoooonnnnttttaaaaiiiinnnnssss(const T& val) const; Returns TTTTRRRRUUUUEEEE if the collection contains an item which is equal to vvvvaaaallll. Returns FFFFAAAALLLLSSSSEEEE otherwise. Equality is measured by the class-defined equality operator. size_t eeeennnnttttrrrriiiieeeessss() const; Returns the number of items currently in the collection. RWBoolean ffffiiiinnnndddd(const T& target, T& k) const; Returns TTTTRRRRUUUUEEEE if the collection contains an item which is equal to ttttaaaarrrrggggeeeetttt PPPPaaaaggggeeee 3333 RRRRWWWWTTTTVVVVaaaallllHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333CCCC++++++++)))) RRRRWWWWTTTTVVVVaaaallllHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333CCCC++++++++)))) and puts the matching object into kkkk. Returns FFFFAAAALLLLSSSSEEEE otherwise and leaves kkkk untouched. Equality is measured by the class-defined equality operator. void iiiinnnnsssseeeerrrrtttt(const T& val); Inserts the value vvvvaaaallll into the collection. RWBoolean iiiissssEEEEmmmmppppttttyyyy() const; Returns TTTTRRRRUUUUEEEE if the collection has no items in it, FFFFAAAALLLLSSSSEEEE otherwise. size_t ooooccccccccuuuurrrrrrrreeeennnncccceeeessssOOOOffff(const T& val) const; Returns the number of items in the collection which are equal to vvvvaaaallll. Equality is measured by the class-defined equality operator. RWBoolean rrrreeeemmmmoooovvvveeee(const T& val); Removes the first object which is equal to the object aaaa and returns TTTTRRRRUUUUEEEE. Returns FFFFAAAALLLLSSSSEEEE if there is no such object. Equality is measured by the class-defined equality operator. size_t rrrreeeemmmmoooovvvveeeeAAAAllllllll(const T& val); Removes all objects which are equal to the object aaaa. Returns the number of objects removed. Equality is measured by the class-defined equality operator. void rrrreeeessssiiiizzzzeeee(size_t N); Changes the number of buckets to NNNN, a relatively expensive operation if there are many items in the collection. PPPPaaaaggggeeee 4444 
